/**
 * 最长公共前缀
 *
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 * 示例 1：
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 *
 * 示例 2：
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 */
public class Num14 {
    public static void main(String[] args) {
        String[] s1 = new String[]{"flower","flow","flight"};
        System.out.println("自己做法解得:"+longestCommonPrefix(s1));
        System.out.println("官方做法解得:"+longestCommonPrefix1(s1));

    }

    //自己完成的版本
    private static String longestCommonPrefix(String[] strs) {
        int[] num = new int[strs.length-1]; // 用num存放每两个String的相同前缀长度
        if (num.length == 0) {
            return strs[0];
        }
        for (int i = 0; i < strs.length-1; i++) { // 遍历strs得到每两个相邻的String的相同前缀长度
            int compareNum = 0; // 临时存放相同前缀长度
            if (Math.min(strs[i].length(), strs[i + 1].length()) == 0) {
                return "";
            }
            for (int j = 0; j < Math.min(strs[i].length(),strs[i+1].length()); j++) { // 遍历两个String的每一个字符，得到相同前缀长度
                if (strs[i].charAt(j) == strs[i + 1].charAt(j)) { //字符相同，继续找
                    compareNum++;
                    if (j == Math.min(strs[i].length(), strs[i + 1].length()) - 1) { //如果找完了两个中最小的那个，找完后直接返回
                        num[i] = compareNum; //字符不同得到前缀长度
                        break;
                    }
                    continue;
                }
                num[i] = compareNum; //字符不同得到前缀长度
                break;
            }
        }
        //找到num中前缀长度最小的值，即为所求值
        int minNum = num[0];
        for (int i = 1; i < num.length; i++) {
            if (minNum > num[i]) {
                minNum = num[i];
            }
        }
        if (minNum == 0) {
            return "";
        }
        return strs[0].substring(0, minNum);

    }


    /**
     * 官方解法，纵向扫描，扫描每个字符串的第一个，匹配是否相等，以此类推
     * @param strs
     * @return
     */
    private static String longestCommonPrefix1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }


}
